//
// Created by bleedingfight on 2020/7/8.
//
#include "fourSum.h"

std::vector<std::vector<int>> fourSum(std::vector<int> &nums, int target) {
<<<<<<< HEAD:cxx/algorithm/src/fourSum.cc
    int size = nums.size();
    std::vector<std::vector<int>> result;
    std::sort(nums.begin(), nums.end());
    if (size < 4)
        return result;
    for (int left = 0; left < size - 3; left++) {
        if (left > 0 && nums[left] == nums[left - 1])continue;
        int right = size - 1;
        while (left < right && right >= 3) {
            int left_second = left + 1;
            int right_second = right - 1;

            while (left_second < right_second) {
                int sum_result = nums[left] + nums[left_second] + nums[right_second] + nums[right];
                if (sum_result == target) {
                    result.push_back({nums[left], nums[left_second], nums[right_second], nums[right]});
                    while (left_second < right_second &&nums[left_second] == nums[left_second + 1])
                        left_second++;
                    while (left_second < right_second && nums[right_second] == nums[right_second - 1])
                        right_second--;
                    if(left_second<right_second){
                        left_second++;
                        right_second--;
                    }

                } else if (left_second < right_second && sum_result > target)
                    right_second--;
                else if (left_second < right_second && sum_result < target)
                    left_second++;
            }

            while (right>3&&nums[right] == nums[right - 1])
                right--;
            right--;
        }
    }
    return result;
}

=======
  int size = nums.size();
  std::vector<std::vector<int>> result;
  std::sort(nums.begin(), nums.end());
  if (size < 4) return result;
  for (int left = 0; left < size - 3; left++) {
    if (left > 0 && nums[left] == nums[left - 1]) continue;
    int right = size - 1;
    while (left < right && right >= 3) {
      int left_second = left + 1;
      int right_second = right - 1;

      while (left_second < right_second) {
        int sum_result =
            nums[left] + nums[left_second] + nums[right_second] + nums[right];
        if (sum_result == target) {
          result.push_back(
              {nums[left], nums[left_second], nums[right_second], nums[right]});
          while (left_second < right_second &&
                 nums[left_second] == nums[left_second + 1])
            left_second++;
          while (left_second < right_second &&
                 nums[right_second] == nums[right_second - 1])
            right_second--;
          if (left_second < right_second) {
            left_second++;
            right_second--;
          }

        } else if (left_second < right_second && sum_result > target)
          right_second--;
        else if (left_second < right_second && sum_result < target)
          left_second++;
      }

      while (right > 3 && nums[right] == nums[right - 1]) right--;
      right--;
    }
  }
  return result;
}
>>>>>>> dev:cxx/algorithm/common/src/fourSum.cc
